﻿using leetcodeAnswer.Code;
using System;
using System.Collections.Generic;
using System.Text;

namespace leetcodeAnswer.Answer
{
    [Answer(
        Index = 4,
        Name = "寻找两个有序数组的中位数",
        Url = "https://leetcode-cn.com/problems/median-of-two-sorted-arrays/",
        Descript = @"给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5")]
    public class No_004_FindMedianSortedArrays
    {
        [AnswerRun]
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            int n = nums1.Length;
            int m = nums2.Length;
            int left = (n + m + 1) / 2;
            int right = (n + m + 2) / 2;
            //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
            return (GetKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + GetKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
        }

        private int GetKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
        {
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;
            //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
            if (len1 > len2) return GetKth(nums2, start2, end2, nums1, start1, end1, k);
            if (len1 == 0) return nums2[start2 + k - 1];

            if (k == 1) return Math.Min(nums1[start1], nums2[start2]);

            int i = start1 + Math.Min(len1, k / 2) - 1;
            int j = start2 + Math.Min(len2, k / 2) - 1;

            if (nums1[i] > nums2[j])
            {
                return GetKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
            }
            else
            {
                return GetKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
            }
        }

        /// <summary>
        /// 验证参数
        /// </summary>
        [AnswerParameter]
        public List<object[]> Parameter { get; set; }

        public No_004_FindMedianSortedArrays()
        {
            Parameter = new List<object[]>() {
                new object[]{ new int[] { 1,3 },new int[] { 2 } },
                new object[]{ new int[] { 1,2 },new int[] { 3,4 } }
            };
        }
    }
}
